package algorithm.middle;

/**
 * 给你一个整数数组 nums 和两个整数：left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组，并返回满足条件的子数组的个数。
 * <p>
 * 生成的测试用例保证结果符合 32-bit 整数范围
 */
public class NumSubarrayBoundedMax795 {

    /**
     * 如果 left≤nums[i]≤right\textit{left} \le \textit{nums}[i] \le \textit{right}left≤nums[i]≤right，令 last1=i\textit{last}_1 = ilast
     * 1
     * ​
     * =i；
     * 否则如果 nums[i]>right\textit{nums}[i] \gt \textit{right}nums[i]>right，令 last2=i\textit{last}_2 = ilast
     * 2
     * ​
     * =i，last1=−1\textit{last}_1 = -1last
     * 1
     * ​
     * =−1。
     * <p>
     * <p>
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/number-of-subarrays-with-bounded-maximum/solutions/1986565/qu-jian-zi-shu-zu-ge-shu-by-leetcode-sol-7it1/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int res = 0;
        //上一个超过区间的
        int lastBig = -1;
        //上一个符合区间的
        int lastSuit = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= left && nums[i] <= right) {
                lastSuit = i;
            } else if (nums[i] > right) {
                lastBig = i;
                lastSuit = -1;
            }
            if (lastSuit != -1) {
                res += lastSuit - lastBig;
            }
        }
        return res;
    }
}
